package com.leetcode.search;

/**
 * leetcode 329 矩阵中最长递增路径  深度优先搜索+记忆
 */
public class Solution329_2 {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int max = 0;
        int[][] memory = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                max = Math.max(max, memory[i][j] != 0 ? memory[i][j] : dfs(matrix, i, j, memory));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int row, int column, int[][] memory) {
        if (row < 0 || row >= matrix.length
                || column < 0 || column >= matrix[row].length) {
            return 0;
        }
        int result = 1;
        // 上
        if (row - 1 >= 0 && matrix[row-1][column] > matrix[row][column]) {
            result = Math.max(result, 1 + (memory[row-1][column] != 0 ? memory[row-1][column] : dfs(matrix, row - 1, column, memory)));
        }
        // 下
        if (row + 1 < matrix.length && matrix[row+1][column] > matrix[row][column]) {
            result = Math.max(result, 1 + (memory[row+1][column] != 0 ? memory[row+1][column] : dfs(matrix, row + 1, column, memory)));
        }
        // 左
        if (column - 1 >= 0 && matrix[row][column-1] > matrix[row][column]) {
            result = Math.max(result, 1 + (memory[row][column-1] != 0 ? memory[row][column-1] : dfs(matrix, row, column - 1, memory)));
        }
        // 右
        if (column + 1 < matrix[row].length && matrix[row][column+1] > matrix[row][column]) {
            result = Math.max(result, 1 + (memory[row][column+1] != 0 ? memory[row][column+1] : dfs(matrix, row, column + 1, memory)));
        }
        memory[row][column] = result;
        return result;
    }

    public static void main(String[] args) {
        Solution329 solution329 = new Solution329();
        int[][] matrix = new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        System.out.println(solution329.longestIncreasingPath(matrix));
    }
}
